Generative Network Automata: A Generalized Framework for Modeling Adaptive Network Dynamics Using Graph Rewritings

摘要

A variety of modeling frameworks have been proposed and utilized in complexsystems studies, including dynamical systems models that describe statetransitions on a system of fixed topology, and self-organizing network modelsthat describe topological transformations of a network with little attentionpaid to dynamical state changes. Earlier network models typically assumed thattopological transformations are caused by exogenous factors, such aspreferential attachment of new nodes and stochastic or targeted removal ofexisting nodes. However, many real-world complex systems exhibit both of thesetwo dynamics simultaneously, and they evolve largely autonomously based on thesystem's own states and topologies. Here we show that, by using the concept ofgraph rewriting, both state transitions and autonomous topology transformationsof complex systems can be seamlessly integrated and represented in a unifiedcomputational framework.We call this novel modeling framework "GenerativeNetwork Automata (GNA)". In this chapter, we introduce basic concepts of GNA,its working definition, its generality to represent other dynamical systemsmodels, and some of our latest results of extensive computational experimentsthat exhaustively swept over possible rewriting rules of simple binary-stateGNA. The results revealed several distinct types of the GNA dynamics.